'''
https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/description/?envType=study-plan-v2&envId=graph-theory
'''
from collections import deque, defaultdict
from typing import List


class Solution:
    # 拓扑排序：
    #   1. 项目有拓扑排序，完成v项目需要先完成之前的项目
    #   2. 组之间有拓扑序，一组必须同时完成，所以，如果当一个组依赖另一个组的项目，则必须先完成另一组的，在完成当前组
    # 最后收集答案
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        def topo_sort(graph, indegree, n):
            res = []
            q = deque([i for i in range(n) if indegree[i] == 0])
            while q:
                u = q.popleft()
                res.append(u)
                for v in graph[u]:
                    indegree[v] -= 1
                    if indegree[v] == 0:
                        q.append(v)
            return res if len(res) == n else []
        # 项目的拓扑排序，图，入度
        item_graph = [[] for _ in range(n)]
        item_indegree = [0 for _ in range(n)]
        for u in range(n):
            for v in beforeItems[u]:    # 完成u，得先完成v。建图v->u
                item_graph[v].append(u)
                item_indegree[u] += 1
        # 组的拓扑排序，图，入度
        # 特殊处理 -1组，让他不为唯一的组。
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1
        group_graph = [[] for _ in range(m)]
        group_indegree = [0 for _ in range(m)]
        for u in range(n):
            for v in beforeItems[u]:
                if group[u] != group[v]:    # 完成u，得先完成v。要完成u这个组，必须先完成v那个组, gv->gu
                    group_graph[group[v]].append(group[u])
                    group_indegree[group[u]] += 1
        item_topo_sort = topo_sort(item_graph, item_indegree, n)
        group_topo_sort = topo_sort(group_graph, group_indegree, m)
        if not item_topo_sort or not group_topo_sort:
            return []
        # 收集答案
        group_items = defaultdict(list)
        for item in item_topo_sort:
            group_items[group[item]].append(item)
        res = []
        for group in group_topo_sort:
            res.extend(group_items[group])
        return res
